#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class BioScore {
public:
	vector<double> v;
	double maxAvg(vector <string>);
	int mapset(char a, char b){
		if(a=='A' && b=='A') return 0;
		if(a=='C' && b=='C') return 1;
		if(a=='G' && b=='G') return 2;
		if(a=='T' && b=='T') return 3;
		if((a=='A' && b=='C') || (a=='C' && b=='A')) return 4;
		if((a=='A' && b=='G') || (a=='G' && b=='A')) return 5;
		if((a=='A' && b=='T') || (a=='T' && b=='A')) return 6;
		if((a=='G' && b=='C') || (a=='C' && b=='G')) return 7;
		if((a=='T' && b=='C') || (a=='C' && b=='T')) return 8;
		if((a=='T' && b=='G') || (a=='G' && b=='T')) return 9;
	}
	void count(vector <string> kset){
		for(int i=0; i<kset.size(); i++){
			for(int j=i+1; j<kset.size(); j++){
				for(int k=0; k<kset[i].size(); k++){
					v[mapset(kset[i][k], kset[j][k])]+=1.0;
				}
			}
		}
	}
	double score(vector<double> a, vector<double> b){
		double ret = 0.0;
		for(int i=0; i<a.size(); i++)
			ret += a[i]*b[i];
		return ret;
	}
};

double BioScore::maxAvg(vector <string> knownSet) {
	v.resize(10);
	count(knownSet);
	int N = knownSet.size();
	sort(v.begin(), v.begin()+4);
	reverse(v.begin(), v.begin()+4);
	sort(v.begin()+4, v.end());
	reverse(v.begin()+4, v.end());
	double ret = -10000;
	vector<double> s(10, 0.0);
	for(s[0]=1.0; s[0]<=10.0; s[0]+=1.0){
		for(s[1]=1.0; s[1]<=10.0; s[1]+=1.0){
			for(s[2]=1.0; s[2]<=10.0; s[2]+=1.0){
				for(s[3]=1.0; s[3]<=10.0; s[3]+=1.0){
					if((int)(s[0] + s[1] + s[2] + s[3]) % 2 == 0){
						s[4] = 10.0;
						s[5] = 10.0;
						s[6] = 10.0 - (s[0] + s[1] + s[2] + s[3]) / 2;
						s[7] = -10.0;
						s[8] = -10.0;
						s[9] = -10.0;
						
						ret = max(ret, score(v, s));
					}
				}
			}
		}
	}
	ret /= (double)(N*(N-1)/2);
	return ret;
}


double test0() {
	string t0[] = {"AAA","AAA","AAC"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	BioScore * obj = new BioScore();
	clock_t start = clock();
	double my_answer = obj->maxAvg(p0);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	double p1 = 30.0;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p1 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p1 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test1() {
	string t0[] = {"ACTGACTGACTG","GACTTGACCTGA"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	BioScore * obj = new BioScore();
	clock_t start = clock();
	double my_answer = obj->maxAvg(p0);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	double p1 = -4.0;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p1 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p1 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test2() {
	string t0[] = {"ACTAGAGAC","AAAAAAAAA","TAGTCATAC","GCAGCATTC"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	BioScore * obj = new BioScore();
	clock_t start = clock();
	double my_answer = obj->maxAvg(p0);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	double p1 = 50.5;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p1 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p1 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}

int main() {
	int time;
	bool errors = false;
	
	time = test0();
	if (time < 0)
		errors = true;
	
	time = test1();
	if (time < 0)
		errors = true;
	
	time = test2();
	if (time < 0)
		errors = true;
	
	if (!errors)
		cout <<"You're a stud (at least on the example cases)!" <<endl;
	else
		cout <<"Some of the test cases had errors." <<endl;
}

//Powered by [KawigiEdit] 2.0!
